/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algoritmo.cruzarpuente;

import java.lang.Math;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JOptionPane;

/**
 *CopyRigth
 * @author CESAR
 */
//esta clase resuelve el problema de cruzar el puente
public class CruzarPuente {
    List<Persona> origen;  //lista que originalmente se encuentran las personas
    List<Persona> destino;  //lista a donde se quiere que llegen las personas
    Integer tiempoT;        //el tiempo total invertido para que cruzar todas las personas
    public static String consola="";  //variable que se utiliza para presentar al final los resultados por consola

    //Constructor de la Clase
    public CruzarPuente() {
        origen = new ArrayList<Persona>();      // se crea el atributo origen de tipo Lista Persona
        destino = new ArrayList<Persona>();     // se crea el atributo destino de tipo Lista Persona
        origen.addAll(generarLista());          //se agrera las personas a la lista origen
        tiempoT = 0;                            //el tiempo total debe iniciar en 0
    }

    //metodo Principal o ejecutor
    public static void main(String[] args) {   //metodo main para llamar a la clase y mostrar resultados
        CruzarPuente cp = new CruzarPuente(); //Se crea una iinstancia de la clase...
        try{                                  //me permite controlar errores en caso de no ingresar numeros
            int caso = Integer.parseInt(JOptionPane.showInputDialog("Ingrese: \n 1: si desea la soluciÃ³n optima \n " //ingreso una cadena mediante una ventana de Dialogo
                                                                    + "2: un numero determinado de interaaciones")); //la cual convierto a entero y la asigno a caso
            int interaccion = 0;                //declaro una variable para la interraciÃ³n
                    if(caso == 1)               //controlo que ingrese 1 u 2
                        cp.mostrarSolucion(caso, interaccion);  //metodo que se encarga de mostrar el resultado
                    else if(caso == 2)
                        interaccion = Integer.parseInt(JOptionPane.showInputDialog("Ingrese el numero de interacciones"));
                        cp.mostrarSolucion(caso, interaccion);  //metodo que se encarga de mostrar el resultado

        }catch(Exception e){   //condiciÃ³n que me controla erroes
            System.out.println("ingrese valores validos");  //mensaje que se muestra cuando se produce un error
        }
    }

    //metodos principales o de mas importancia
    public final List<Persona> generarLista() {
        // este metodo se utiliza par agregar las personas (A, B, C, D) a la lista de oirgen
        //con un tiempo de (1, 2, 5, 10) respectivamente
        Persona a = new Persona();
        List<Persona> personas = new ArrayList<Persona>();
        a.setNombre("A");
        a.setTiempo(1);
        personas.add(a);
        a = new Persona();
        a.setNombre("B");
        a.setTiempo(2);
        personas.add(a);
        a = new Persona();
        a.setNombre("C");
        a.setTiempo(5);
        personas.add(a);
        a = new Persona();
        a.setNombre("D");
        a.setTiempo(10);
        personas.add(a);
        return personas;
    }
    public void mostrarSolucion(int caso, int num_interacciones){
     /*En el metodo mostrarResultados() me presenta los resultados al cruzar el Puente.
      Recibe como parametro caso de tipo entero que represnta
        1 (solucion optima): una busqueda aleatorea hasta llegar a la solucion Ã³ptima que es 17 minutos dados los valores de origen
     *  2 (solucion con menor tiempo): una busqueda aleatoria con un limite de busqueda dando como resultado el menor tiempo al cruzar el puente
     * num_interacciones tipo entero que es: el numero de interacciones que se desea generar.
      */
        long t_ejecucion = System.currentTimeMillis();      //se utiliza para sacer el tiempo total de ejecuciÃ³n en milisegundos
        CruzarPuente cp ;       //se llama al constructor de la clase CruzarPuente
        List<Persona> x = new ArrayList<Persona>();     //lista adicional que servira para escoger las personas que cruzaran el puente con una busqueda aleatorea
        List<Integer> t = new ArrayList();      //lista tipo entero para almacenar los tiempo de cada busqueda o iteraciÃ³n
        int pasadas = 0;                        //variable para determinar el nÃºmero de pasadas
        System.out.println("Soluciones");
            do{             //desde aqui se comienza el ciclo de todas las iteracciones que se generaran hasta encontrar la soluciÃ³n Ã³ptima
                cp = new CruzarPuente();                        // se debe llamar al constructor por cada interacciÃ³n para que las listas se inicialicen
                long t_eje_pasada = System.nanoTime();          // variable de inicio para calcular el tiempo de ejecucion en nanosegundos
                consola += "Lista original \n";
                consola += cp.imprimirLista(cp.getOrigen());    //se imprime el estado original de las listas
                int paso = 1;                                   //variable para calcular el numero de paso
                //<<<-----------------------
                while(cp.getOrigen()!=null && paso < 4 ){       // ce controla que todas las Personas crucen, para ello la lista de origen debe quedar vacia
                x = cp.escoger(cp.getOrigen());                 // se escoge al azar dos personas de las lista de origen
                cp.cruzar(x.get(0), x.get(1));                  // para cruzar el puente se debe enviar dos personas de la lista x
                                               // la lista x siempre va a tener dos personas se le envia como parametro la  posicion 0 y 1 al mÃ©todo cruzar
                if(cp.getDestino().size()<4)                  //se controla que si estÃ¡n todas las Personas en la lista de destino ya no regresen
                   cp.regresar(cp.getDestino());                // metodo para regresar una Persona de la lista de destino
                paso ++;                                        //imcremento del paso en 1
                x = null;                                       //la lista x nuevamente debe estar vacia
                }                                               //Se repite el mientras hasta que todas las Personas hayan cruzado
                //------------------------->>>
                pasadas += 1;                           //incremento para controlar cada interraciÃ³n
                t.add(cp.getTiempoT());                 //agrego el tiempo al cruzar el puente, esa interraciÃ³n en una lista de tiempos
                System.out.println(consola);  //Se presenta la variable consola por pantalla.
                System.out.println("Tiempo Invertido para cruzar el puenete es: "+cp.getTiempoT() + " minutos"); //se presenta el tiempo total de todas las personas al cruzar el puente
                long t_eje_pasada1 = System.nanoTime()-t_eje_pasada;    // variable entera que se le asigna el tiempo de ejecucion en nanosegundos - el tiempo de la variable que inicio el tiempo de ejecuciÃ³n
                System.out.println("Tiempo de ejecución por pasada: "+t_eje_pasada1+" nanosegundos"); // se muestra el tiempo de ejecuciÃ³n
                System.out.println("----------------------------------------------");
                consola = "";                           //la variable inicializa en vacio
            }while(cp.evaluarSolucion(caso, pasadas, num_interacciones));  //se controla hasta cuando se va a
                                                            //repetir el ciclo. verificando si es verdadero o falso el metodo evaluarSoluciÃ³n()
            System.out.println("Se generaron: "+pasadas+" Interacciones "); //se muestra el numero de interacciones
            int tMenor = t.get(0);          //variable para calcular el tiempo menor de todas las interacciones
            int tMayor = tMenor;            //variable para calcular el tiempo mayor de todas las interacciones
            //........................  for de colecciones para verificar que tiempo es menor
            System.out.print("Lista de tiempos: ");
            for (int tiempo : t) {
                System.out.print(tiempo+" ");
                if(tiempo < tMenor)
                    tMenor = tiempo;
                else if(tiempo > tMayor)
                    tMayor = tiempo;
            }
            //........................
            System.out.println(" \n\n el mejor tiempo es: "+ tMenor);
            System.out.println(" el mayor tiempo es: "+ tMayor);
            long t_ejecucion_total = System.currentTimeMillis() - t_ejecucion;
            System.out.println("El tiempo de ejecución total es: "+t_ejecucion_total+ " milisegundos");
    }
    public void cruzar(Persona p1, Persona p2)  {
    /* Este metodo permite cruzar las dos personas recibidas como parametros, de la liste de origen a la lista de destino
     */
        List<Persona> oaux = new ArrayList<Persona>();  //lista auxiliar que me permitira remplazar la lista de origen quitandole las dos personas
        oaux.addAll(getOrigen());   //agregarmos todos las personas de la lista de origen
        getDestino().add(p1);       //agregamos las dos personas a la lista de destino, es decir las 2 personas cruzaron
        getDestino().add(p2);
        int t = verificartiempos(p1, p2);  //se almacena el tiempo que retorna el metodo en t para asignarlo al tiempo final
        tiempoT += t;  //se agrega el tiempo
          //<<--.  ciclo que me permite eliminar las Personas que ya cruzaron de la lista de origen
        for (Persona persona1 : getOrigen()) {
            if(persona1 ==p1 || persona1==p2)
                oaux.remove(persona1);   //se elimina de la lista auxiliar
        }       //-->>
        consola += p1 + " "+ p2 + "  ==>  " + t + "\n";
        setOrigen(oaux);         //se remplaza la lista de origen por la auxiliar quedando asi las Personas que no cruzan el Puente
    }
    public void regresar(List<Persona> p) {
    /*Este metodo me permite regresar una Persona de la lista de destino hacia la lista de origen
     * Recibe como parametro una lista que representa la lista de Destino actual
     Hay que tener en cuenta que para regresar una Persona debe tener menor tiempo de todas */

        int t = p.get(0).getTiempo();   //variable que me optine el tiempo de la Persona de la primera posiciÃ³n de la lista
        int pos=0;                      //se usara esta variable para optener la posiciÃ³n de esa persona en la lista de destino actual
        //<<--- Este ciclo se usa para optener el menor tiempo de una persona y la posiciÃ³n, de la lista de Destino actual
        for (int i = 0; i < p.size(); i++) {
            if(p.get(i).getTiempo()<t){
                t = p.get(i).getTiempo();
                pos = i;
            }
        } //--->>
        consola += p.get(pos)+"  <==  " +t+"\n";    //se agrega la persona que regresa y su respectivo tiempo a la variable consola
        getOrigen().add(p.get(pos));                //Se agrega la Persona con menor tiempo a la lista de origen
        p.remove(pos);                              //Se elimina la persona que regreso de la lista de destino actual
        tiempoT += t;                               //Se agrega el tiempo de regreso a la varible del tiempo total para cruzar el puente
        setDestino(p);                              //se remplaza la lista de destino por la acutal ya quitado la persona que regreso
    }
    public List<Persona> escoger(List<Persona> p) {
    /*MÃ©todo que me permite coger de la lista enviada como parametro dos personas al azar
     *agregarlas a una lista auxiliar y retornar esa lista...
     */
        List<Persona> per = new ArrayList<Persona>();   //Lista auxiliar para almacenar las personas seleccionas al azar
        int num_aleatorio = aleatorio(p.size()-1);      //se agrega un numero del metodo aleatoreo que representa la posiciÃ³n de la lista
                                                        //el valor p.size()-1 es el tamamo de la lista o numero de personas que tiene
        per.add(p.get(num_aleatorio));      //se agrega a la lista auxiliar una persona de lista lista p con la posiciÃ³n num_aleatorio
        int aux = num_aleatorio;            //varible que se utilizara para verificar que no se selecciones el mismo numero
        //<<--- este ciclo hace que mientras el numero aleatorio sea diferente del primero no termine el ciclo
        while(aux == num_aleatorio)
            num_aleatorio=aleatorio(p.size()-1);

        per.add(p.get(num_aleatorio));         //una ves Ã³ptenido la otra posiciÃ³n se agrega a la lista auxiliar la otra persona
        return per;         //por ultimo se retorna la lista con los personas seleccionas al azar......
    }

    // Metodos alternos de ayuda para la soluciÃ³n
    public String imprimirLista(List<Persona> p) {
        //este metodo me retorna una cadena de texto tomado como parametro una lista
        //la cadena contiene cada uno le las personas para ser presentadas
        String x = "";
        for (Persona b : p) {  //for de colecciones para rrecorrer cada uno las personas de la lista
             x += b+"  ";  //se agrega  cada persona a la cadena separadas con un enter
        }
        x += "\n \n";  //se agrega 2 espacios para hacer la presentaciÃ³n mÃ¡s elegante
        return x;   //retorna  la cadena x con todas las personas
    }
    public int aleatorio(int longitud) {
    /*Este mÃ©todo retorna un numero aleatorio dado como parametro (un numero entero longitud) que representa el tamaÃ±o de la lista
     *es utilizado en el metodo escoger()
     */
        int x=0;
        //<<---- ciclo que me repite el nÃºmero de veces hasta que el valor de x sea menor a la longitud osea puede ser 0, 1, 2 y 3
        do{
        x = (int)(Math.random()*10);
        }while(x>longitud); //-->>
        return x;       //retonra la posiciÃ³n
    }
    public int verificartiempos(Persona p1, Persona p2) {
      /* Este metodo es utilizado en el metodo cruzar() y me retorna el tiempo mayor de las dos personas recibidas como parametros
       *
       */
        if (p1.getTiempo() > p2.getTiempo()) {
            return p1.getTiempo();
        } else {
            return p2.getTiempo();
        }
    }
    public boolean evaluarSolucion(int valor, int pasadas, int num_interacciones){
        /* Este metodo es invocado desde mostrar resultado y me permite evaluar
         1: si se generan interaaciones hasta llegar al tiempo Ã³ptimo o
         2: generar soluciones con un nÃºmero determinado de interacciones...
         *  sus parametros representan:
         * valor : representa si es la opcion 1 o 2
         * pasadas: determina el nÃºmero actual de interacion
         * num_interacciones: es el limite de las interacciones que el usuario ingresa x teclado
         */
        boolean ban = false;
        if(valor == 1){
            if(tiempoT > 17)
                ban = true;             //devolvera verdadero siempre cuando el tiempo sea mayor a 17
        } else if (valor == 2) {
            if(pasadas < num_interacciones)
                ban = true;             //devolvera verdadero siempre cuando las pasadas no llegen al limite
             else
                ban = false;            //cuando no se cumplen ninguna de las condiciones antes mensionadas
        }
        return ban;             //retorna el valor
    }

    //Metodos de get y set de los atributos
    public List<Persona> getDestino() {
        return destino;
    }
    public void setDestino(List<Persona> destino) {
        this.destino = destino;
    }
    public List<Persona> getOrigen() {
        return origen;
    }
    public void setOrigen(List<Persona> origen) {
        this.origen = origen;
    }
    public Integer getTiempoT() {
        return tiempoT;
    }
    public void setTiempoT(Integer tiempoT) {
        this.tiempoT = tiempoT;
    }
}
